package leetcode_21_40;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class longestValidParentheses_32 {
    /**
     * 没搞出来，情况复杂，我的想法处理不了
     * 最长有效括号
     * ()(()
     * 每一个左括号找到其对应的右括号算作一段，连续的段落长度和就是一段有效括号
     * @param s
     * @return
     */
    public static int longestValidParentheses(String s) {
        int left=0,right=0;    //实时左右括号数
        List<Integer>longs=new ArrayList<>();
        int nowLong=0                  //（）(())  一段闭合括号的长度
                ,maxLong=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('){
                left++;
            }
            else{
                if(left>right)                      //满足（   数量大于  ） 才可以增加nowLong的长度
                    nowLong+=2;               //每加一个 ），说明有一个（  匹配到，长度+2
                right++;
                if(left==right){
                    longs.add(nowLong);
                    nowLong=0;
                }
                if(i==s.length()-1 && right< left){               //()((())情况
                    nowLong=2*right;
                    longs.add(nowLong);
                }
            }
            //判断是否该进行下一段判定
            if(left<= right || i==s.length()-1) {                          //当 ）数量大于等于（ ，左右括号数直接全部清零

                int sumLong=0;                //连续的有效段落之和长度
                for (int t:longs)
                    sumLong+=t;
                longs.clear();
                left=right=0;
                if(sumLong>maxLong)       //如果当前匹配长度为最长，更新
                    maxLong=sumLong;
                sumLong=0;
            }
        }
        return maxLong;
    }

    /**
     * 动态规划
     * 方法思路类似我自己写的，具体操作更为巧妙，规避了很多问题
     * 定义 dp[i]\textit{dp}[i]dp[i] 表示以下标 iii 字符结尾的最长有效括号的长度
     * @param s
     * @return
     */
    public static int longestValidParentheses2(String s) {
        int maxans = 0;
        int[] dp = new int[s.length()];
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {           //s[i]=‘)’ 且 s[i−1]=‘(’s[i - 1] = \text{‘(’}s[i−1]=‘(’，也就是字符串形如 “……()”
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;   //将之前有效子字符串的长度增加 2。
                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {              //s[i]=‘)’ 且 s[i−1]=‘)’s[i - 1] = \text{‘)’}s[i−1]=‘)’，也就是字符串形如 “……))
                                                                                                                        //并且 如果 s[i−dp[i−1]−1]=‘(’，  类似  （  ()()  )     找到上一部分有效括号之前是否右对应的（  ,就可以完成匹配
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxans = Math.max(maxans, dp[i]);
            }
        }
        return maxans;
    }
}
